import java.util.Arrays;

/**
 * 归并排序
 * 分治思想
 * 分：每次折半划分，直至只有一个元素
 * 合：两个有序的数组合并
 */
public class MergeSort {


    public int[] sort(int[] nums){
        int len = nums.length;
        if(len<2) return nums;
        int middle = len/2;
        int[] left = Arrays.copyOfRange(nums, 0, middle);
        int[] right = Arrays.copyOfRange(nums, middle, len);

        return merge(sort(left),sort(right));

    }

    /**
     * 将两个有序数组合并成一个有序的数组
     * @param left
     * @param right
     * @return
     */
    private int[] merge(int[] left,int[] right){
        int l_len = left.length,r_len = right.length;
        int[] result = new int[l_len+r_len];
        int i=0,j=0;
        while (i<l_len&&j<r_len){
            if(left[i]<=right[j]){
                result[i+j] = left[i];
                i++;
            }else {
                result[i+j] = right[j];
                j++;
            }
        }
        for (; i < l_len; i++) {
            result[i+j] = left[i];
        }
        for (;j<r_len;j++){
            result[i+j] = right[j];
        }


        return result;

    }

    public static void main(String[] args) {
        int[] nums = {9,4,6,-3,10,3,13,60};
        MergeSort mergeSort = new MergeSort();
        int[] sort = mergeSort.sort(nums);
        for (int i = 0; i < sort.length; i++) {
            System.out.print(sort[i]+" ");
        }
    }
}
